{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Paint House II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minCostII"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #粉刷房子 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>假如有一排房子共有&nbsp;<code>n</code>&nbsp;幢，每个房子可以被粉刷成 <code>k</code>&nbsp;种颜色中的一种。房子粉刷成不同颜色的花费成本也是不同的。你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。</p>\n",
    "\n",
    "<p>每个房子粉刷成不同颜色的花费以一个 <code>n x k</code> 的矩阵表示。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<code>costs[0][0]</code> 表示第 <code>0</code>&nbsp;幢房子粉刷成 <code>0</code> 号颜色的成本；<code>costs[1][2]</code>&nbsp;表示第 <code>1</code> 幢房子粉刷成 <code>2</code> 号颜色的成本，以此类推。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回 <em>粉刷完所有房子的最低成本</em>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>costs = [[1,5,3],[2,9,4]]\n",
    "<strong>输出: </strong>5\n",
    "<strong>解释: \n",
    "</strong>将房子 0 刷成 0 号颜色，房子 1 刷成 2 号颜色。花费: 1 + 4 = 5; \n",
    "或者将 房子 0 刷成 2 号颜色，房子 1 刷成 0 号颜色。花费: 3 + 2 = 5. </pre>\n",
    "\n",
    "<p><strong>示例&nbsp;<strong>2:</strong></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> costs = [[1,3],[2,4]]\n",
    "<strong>输出:</strong> 5\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>costs.length == n</code></li>\n",
    "\t<li><code>costs[i].length == k</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 100</code></li>\n",
    "\t<li><code>2 &lt;= k &lt;= 20</code></li>\n",
    "\t<li><code>1 &lt;= costs[i][j] &lt;= 20</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>您能否在&nbsp;<code>O(nk)</code> 的时间复杂度下解决此问题？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [paint-house-ii](https://leetcode.cn/problems/paint-house-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [paint-house-ii](https://leetcode.cn/problems/paint-house-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,5,3],[2,9,4]]', '[[1,3],[2,4]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        n = len(costs)\n",
    "        k = len(costs[0])\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            \n",
    "            # Find the colors with the minimum and second to minimum\n",
    "            # in the previous row.\n",
    "            min_color = second_min_color = None\n",
    "            for color in range(k):\n",
    "                cost = costs[i - 1][color]\n",
    "                if min_color is None or cost < costs[i - 1][min_color]:\n",
    "                    second_min_color = min_color\n",
    "                    min_color = color\n",
    "                elif second_min_color is None or cost < costs[i - 1][second_min_color]:\n",
    "                    second_min_color = color\n",
    "            for j in range(k): \n",
    "                if j == min_color:\n",
    "                    costs[i][j] += costs[i-1][second_min_color]\n",
    "                else:\n",
    "                    costs[i][j] += costs[i-1][min_color]\n",
    "        \n",
    "        return min(costs[n-1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "# O(N*C) N rooms count C color count\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        room_len = len(costs)\n",
    "        if not room_len:\n",
    "            return 0\n",
    "        color_len = len(costs[0])\n",
    "        if not color_len:\n",
    "            return 0\n",
    "        # state dp[0~n-1][0~2] dp[i][j] 第i个房间涂j颜色的花费最小值\n",
    "        dp = [[0 for _ in range(color_len)] for _ in range(room_len)]\n",
    "        # init\n",
    "        for idx in range(color_len):\n",
    "            dp[0][idx] = costs[0][idx]\n",
    "        # tranfer: dp[i][j] = min(dp[i-1][:j or j+1:] + costs[i][j])\n",
    "        for r_idx in range(1, room_len):\n",
    "            for c_idx in range(color_len):\n",
    "                pre_min_costs = [dp[r_idx - 1][pre_c_idx] for pre_c_idx in\n",
    "                                 range(color_len) if pre_c_idx != c_idx]\n",
    "                dp[r_idx][c_idx] = min(pre_min_costs) + costs[r_idx][c_idx]\n",
    "        # print(costs)\n",
    "        # print(dp)\n",
    "        # result\n",
    "        return min([dp[room_len-1][c_idx] for c_idx in range(color_len)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        if not costs: return 0\n",
    "        l, k = len(costs), len(costs[0])\n",
    "        for i in range(1, l):\n",
    "            for j in range(k):\n",
    "                tmp = costs[i-1][:]\n",
    "                tmp.pop(j)\n",
    "                costs[i][j] += min(tmp)\n",
    "        return min(costs[:][-1])\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        costs_length = len(costs)\n",
    "        if costs_length == 0:\n",
    "            return 0\n",
    "\n",
    "        cost_matrix = [[0] * len(costs[0]) for i in range(costs_length)]\n",
    "        cost_matrix[0] = costs[0][:]\n",
    "\n",
    "        for i in range(1, costs_length):\n",
    "            houses = costs[i]\n",
    "            for j in range(len(houses)):\n",
    "                lst = cost_matrix[i-1][:]\n",
    "                del lst[j]\n",
    "                cost_matrix[i][j] = houses[j] + min(lst)\n",
    "\n",
    "        return min(cost_matrix[len(cost_matrix)-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        # n houses, can be painted with one of the k colors\n",
    "        # cost of each color is different.\n",
    "        # no two adjacent houses have the same color.\n",
    "        # Time complexity: O(NK)\n",
    "        # Space complexity: O(K)\n",
    "        \n",
    "        if costs == []: return 0\n",
    "        row, col = len(costs), len(costs[0])\n",
    "        \n",
    "        dp = costs[0][:]\n",
    "        for i in range(1, row):\n",
    "            firVal, secVal = float('inf'), float('inf')\n",
    "            for j in range(col):\n",
    "                if dp[j] < firVal:\n",
    "                    firVal, secVal = dp[j], firVal\n",
    "                elif dp[j] < secVal:\n",
    "                    secVal = dp[j]\n",
    "            for j in range(col):\n",
    "                if dp[j] != firVal: dp[j] = costs[i][j] + firVal\n",
    "                else: dp[j] = costs[i][j] +  secVal\n",
    "        return min(dp)\n",
    "\t\t\t\t\t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        if len(costs) == 0: return 0\n",
    "        dp = [[0 for _ in range(len(costs[0]))] for _ in range(len(costs))]\n",
    "        # dp[i][k] = min(dp[i-1][{r,g,b}-k])+costs[i][k]\n",
    "        dp[0] = costs[0]\n",
    "        for i in range(1, len(costs)):\n",
    "            for k in range(len(costs[i])):\n",
    "                l = list(range(len(costs[i])))\n",
    "                l.remove(k)\n",
    "                temp = dp[i-1][l[0]]\n",
    "                for j in range(1, len(l)):\n",
    "                    temp = min(dp[i-1][l[j]], temp)\n",
    "                dp[i][k] = temp + costs[i][k]\n",
    "        # print(dp)\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        n = len(costs)\n",
    "        if not n:\n",
    "            return 0\n",
    "        m = len(costs[0])\n",
    "        for i in range(1, n):\n",
    "            for j in range(m):\n",
    "                val = float('inf')\n",
    "                for k in range(m):\n",
    "                    if k == j:\n",
    "                        continue\n",
    "                    val = min(val, costs[i-1][k])\n",
    "                costs[i][j] += val\n",
    "        \n",
    "        return min(costs[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        if not costs:\n",
    "            return 0\n",
    "        n=len(costs)\n",
    "        k=len(costs[0])\n",
    "        if k==0:\n",
    "            return 0\n",
    "        dp=[[0]*k for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for c in range(k):\n",
    "                if i==0:\n",
    "                    dp[0][c]=costs[0][c]\n",
    "                    continue\n",
    "                dp[i][c]=min(dp[i-1][co] for co in range(k) if co!=c)+costs[i][c]\n",
    "        return min(dp[n-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        if not costs or not costs[0]:\n",
    "            return 0\n",
    "\n",
    "        s1, s2 = len(costs), len(costs[0])  # s1=房子数量，s2=颜色数量\n",
    "\n",
    "        dp = [[0] * s2 for _ in range(s1)]\n",
    "        for i2 in range(s2):\n",
    "            dp[0][i2] = costs[0][i2]\n",
    "\n",
    "        for i1 in range(1, s1):\n",
    "            for i2 in range(s2):\n",
    "                dp[i1][i2] = costs[i1][i2] + min(dp[i1 - 1][ii2] for ii2 in range(s2) if ii2 != i2)\n",
    "\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        if not costs:\n",
    "            return 0\n",
    "        n, k = len(costs), len(costs[0])\n",
    "        @lru_cache\n",
    "        def dfs(index: int, pre: int) -> int:\n",
    "            if index == n:\n",
    "                return 0\n",
    "            ret = float('inf')\n",
    "            for i in range(k):\n",
    "                if i == pre: continue\n",
    "                ret = min(ret, costs[index][i] + dfs(index + 1, i))\n",
    "            return ret    \n",
    "        return dfs(0, -1);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        n = len(costs)\n",
    "        if n == 0: return 0\n",
    "        k = len(costs[0])\n",
    "        # dp = [[0]*k for i in range(n)]\n",
    "        for i in range(1,n):\n",
    "            for j in range(k):\n",
    "                flag = 1\n",
    "                temp = costs[i][j]\n",
    "                for m in range(k):\n",
    "                    if j != m:\n",
    "                        if flag:\n",
    "                            costs[i][j] += costs[i-1][m]\n",
    "                            flag = 0\n",
    "                        else:\n",
    "                            costs[i][j] = min(costs[i][j],costs[i-1][m] + temp)\n",
    "        # print(costs)\n",
    "        return min(costs[n-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        m, n = len(costs), len(costs[0])\n",
    "\n",
    "        dp = costs[0]\n",
    "\n",
    "        for i in range(1, len(costs)):\n",
    "            first, second = None, None\n",
    "            for n in dp:\n",
    "                if first is None:\n",
    "                    first = n\n",
    "                    continue\n",
    "                if n <= first:\n",
    "                    second = first\n",
    "                    first = n\n",
    "                elif second is None or n < second:\n",
    "                    second = n\n",
    "\n",
    "            for j in range(len(dp)):\n",
    "                if dp[j] == first:\n",
    "                    dp[j] = second + costs[i][j]\n",
    "                else:\n",
    "                    dp[j] = first + costs[i][j]\n",
    "            \n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        n = len(costs)\n",
    "        k = len(costs[0])\n",
    "        dp = [[100*21]*k for _ in range(n)]\n",
    "\n",
    "        dp[0] = costs[0]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(k):\n",
    "                for z in range(k):\n",
    "                    if j == z:\n",
    "                        continue\n",
    "                    dp[i][j] = min(dp[i][j], dp[i-1][z]+costs[i][j])\n",
    "        \n",
    "        return min(dp[n-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        n = len(costs)\n",
    "        colors = len(costs[0])\n",
    "        dp = [[0] * colors for _ in range(n+1)]\n",
    "        for i in range(1, n+1):\n",
    "            for k in range(colors):\n",
    "                dp[i][k] = min(dp[i-1][:k]+dp[i-1][k+1:]) + costs[i-1][k]\n",
    "        return min(dp[n])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        # dp[i][j]表示从0-i号房子被粉刷且i号房子被粉刷成颜色j的最小花费\n",
    "        n_h = len(costs)\n",
    "        n_c = len(costs[0])\n",
    "        dp = [[0 for i in range(n_c)] for j in range(n_h)]\n",
    "        \n",
    "        for h in range(n_h):\n",
    "            print(dp)\n",
    "            for c in range(n_c):\n",
    "                if h == 0:\n",
    "                    dp[h][c] = copy.deepcopy(costs[h][c])\n",
    "                    \n",
    "                else:\n",
    "                    mincol = 1e9\n",
    "                    for j in range(n_c):\n",
    "                        if j != c:\n",
    "                            mincol = min(mincol, copy.deepcopy(dp[h-1][j]))\n",
    "                            # print(h-1, c,j, dp, mincol)\n",
    "                    dp[h][c] = mincol + copy.deepcopy(costs[h][c])\n",
    "                    # print(h,c,mincol, dp[h][c], costs[h][c])\n",
    "        # print(dp)\n",
    "        res = 1e9\n",
    "        for c in range(n_c):\n",
    "            res = min(res, dp[n_h-1][c])\n",
    "        return res\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        n = len(costs)\n",
    "        k = len(costs[0])\n",
    "\n",
    "        dp = dict()\n",
    "        return self.func(costs, 0, -1, dp)\n",
    "\n",
    "    def func(self, costs, pos, color, dp):\n",
    "        if (pos, color) in dp:\n",
    "            return dp[(pos, color)]\n",
    "        n = len(costs)\n",
    "        k = len(costs[0])\n",
    "\n",
    "        if pos >= len(costs):\n",
    "            res = 0\n",
    "        else:\n",
    "            min_color = -1\n",
    "            min_cost = -1\n",
    "            for ncolor in range(k):\n",
    "                if ncolor != color:\n",
    "                    ncost = costs[pos][ncolor] + self.func(costs, pos+1, ncolor, dp)\n",
    "                    if min_cost < 0 or min_cost > ncost:\n",
    "                        min_color = ncolor\n",
    "                        min_cost = ncost\n",
    "            res = min_cost\n",
    "        dp[(pos, color)] = res\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        # 房子颜色\n",
    "        m, n = len(costs), len(costs[0])\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        dp[0] = costs[0]\n",
    "        for i in range(1, m):\n",
    "            min_2 = self.min_2(dp[i - 1])\n",
    "            for k in range(n):\n",
    "                dp[i][k] = costs[i][k] + (min_2[0][0] if k != min_2[0][1] else min_2[1][0])\n",
    "        print(dp)\n",
    "        return min(dp[-1])\n",
    "\n",
    "    def min_2(self, l):\n",
    "        s = SortedList()\n",
    "        for i, val in enumerate(l):\n",
    "            s.add((val, i))\n",
    "            if len(s) == 3:\n",
    "                s.pop()\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        # min1, min2 = 0, 0\n",
    "        # ind = 0\n",
    "        # kinds = len(costs[0])\n",
    "        # for cost in costs:\n",
    "        #     for i in range(kinds):\n",
    "        #         if i != ind:\n",
    "        #             cost[i] += min1   \n",
    "        #         else: \n",
    "        #             cost[i] += min2\n",
    "        #     min1 = min(cost)\n",
    "        #     ind = cost.index(min1)\n",
    "        #     min2 = min(cost[:ind] + cost[ind + 1:])\n",
    "\n",
    "        # return min1\n",
    "\n",
    "        min1, min2, ind = 0, 0, 0\n",
    "        for cost in costs:\n",
    "            m1, m2, ind_ = inf, inf, 0\n",
    "            for i, new in enumerate(cost):\n",
    "                total = new + min1 if i != ind else new + min2\n",
    "                if total < m1:\n",
    "                    m1, m2, ind_ = total, m1, i\n",
    "                elif total < m2:\n",
    "                    m2 = total\n",
    "            min1, min2, ind = m1, m2, ind_\n",
    "        return min1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        n, m = len(costs), len(costs[0])\n",
    "        dp = [[0 for _ in range(m)] for _ in range(n)]\n",
    "        # 记录dp[i-1][j]的最小值和次小值\n",
    "        min_1, min_2 = 0, 0\n",
    "        for i in range(n):\n",
    "            tmp_1, tmp_2 = inf, inf\n",
    "            for j in range(m):\n",
    "                if i:\n",
    "                    if dp[i - 1][j] == min_1:\n",
    "                        dp[i][j] = min_2\n",
    "                    else:\n",
    "                        dp[i][j] = min_1\n",
    "                dp[i][j] += costs[i][j]\n",
    "                if dp[i][j] < tmp_1:\n",
    "                    tmp_2 = tmp_1\n",
    "                    tmp_1 = dp[i][j]\n",
    "                elif dp[i][j] < tmp_2:\n",
    "                    tmp_2 = dp[i][j]\n",
    "            min_1, min_2 = tmp_1, tmp_2\n",
    "        return min(dp[n - 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        n, m = len(costs), len(costs[0])\n",
    "        dp = [[inf for _ in range(m)] for _ in range(n)]\n",
    "        for i in range(m):\n",
    "            dp[0][i] = costs[0][i]\n",
    "        for i in range(1, n):\n",
    "            for j in range(m):\n",
    "                for k in range(m):\n",
    "                    if j == k:\n",
    "                        continue\n",
    "                    dp[i][j] = min(dp[i][j], dp[i - 1][k])\n",
    "                dp[i][j] += costs[i][j]\n",
    "        return min(dp[n - 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        dp = [[0 for _ in costs[0]] for _ in costs]\n",
    "        dp[0] = costs[0]\n",
    "        for idx in range(1, len(costs)):\n",
    "            for i in range(len(costs[0])):\n",
    "                tmp = 10**9\n",
    "                for j in range(len(costs[0])):\n",
    "                    if i != j:\n",
    "                        print(i, j)\n",
    "                        tmp = min(tmp, dp[idx-1][j] + costs[idx][i])\n",
    "                dp[idx][i] = tmp\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        n = len(costs)\n",
    "        @cache\n",
    "        def dfs(i,pre):\n",
    "            if i>=n:\n",
    "                return 0\n",
    "            ans = inf\n",
    "            for j,c in enumerate(costs[i]):\n",
    "                if j != pre:\n",
    "                    ans = min(ans,dfs(i+1,j)+c)\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0,-1)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        return self.answer_1(costs)\n",
    "\n",
    "    def answer_1(self, costs):\n",
    "        n = len(costs)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "\n",
    "        k = len(costs[0])\n",
    "\n",
    "        @lru_cache(maxsize=None)\n",
    "        def _memo_resolve(house_index, color):\n",
    "            if house_index == n - 1:\n",
    "                return costs[house_index][color]\n",
    "\n",
    "            tmp_cost = float(\"inf\")\n",
    "\n",
    "            for next_color in range(k):\n",
    "                if next_color == color:\n",
    "                    continue\n",
    "\n",
    "                tmp_cost = min(tmp_cost, _memo_resolve(house_index + 1, next_color))\n",
    "            return costs[house_index][color] + tmp_cost\n",
    "\n",
    "        cost = float(\"inf\")\n",
    "\n",
    "        for index in range(k):\n",
    "            cost = min(cost, _memo_resolve(0, index))\n",
    "        return cost"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
